/*
 * @lc app=leetcode.cn id=2151 lang=cpp
 *
 * [2151] 基于陈述统计最多好人数
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        n_ = statements.size();
        isGoodFlag_.resize(n_, 2);

        TraceBack(statements, 0);

        return maxGood_;
    }
private:
    int n_;
    int maxGood_ = 0;
    // 0 : bad
    // 1 : good
    // 2 : unknown
    std::vector<int> isGoodFlag_;
private:
    // return false when conflicts occur
    bool TraceBack(vector<vector<int>>& statements, int index) {
        // check end
        if (index == n_) {
            // let me see how many 0 (bad)
            int counter = 0;
            for (int flag : isGoodFlag_) {
                if (flag != 0) counter += 1;
            }
            if (counter > maxGood_) maxGood_ = counter;
            return true;
        }

        // check already set current person good
        if (isGoodFlag_[index] == 1) {
            std::vector<int> isGoodFlag_bak = isGoodFlag_;
            // check conflicts, if conflicts occur, return false
            auto& currentStatement = statements[index];
            for (int i=0;i<n_;++i) {
                if (currentStatement[i] == 1) {
                    if (isGoodFlag_[i] == 0) return false;
                    else isGoodFlag_[i] = 1;
                }
                if (currentStatement[i] == 0) {
                    if (isGoodFlag_[i] == 1) return false;
                    else isGoodFlag_[i] = 0;
                }
            }
            // no conflict, go on
            bool assumeSuccess = TraceBack(statements, index + 1);
            // remember to trace back because we changed the flag vec
            isGoodFlag_ = isGoodFlag_bak;
            return assumeSuccess;
        } 

        // check already set current person bad
        else if (isGoodFlag_[index] == 0) {
            // no need to check conflicts because we assumed him bad
            // just go on
            return TraceBack(statements, index + 1);
        }

        // current person 2 (not mentioned), we need to assume him goog or bad
        else {
            std::vector<int> isGoodFlag_bak = isGoodFlag_;
            // check if we can assume him good,
            if (1) {
                bool canAssumeGood = true;
                for (int i=0;i<n_;++i) {
                    if (statements[index][i] == 0 and isGoodFlag_[i] == 1) {
                        canAssumeGood = false;
                        break;
                    }
                    if (statements[index][i] == 1 and isGoodFlag_[i] == 0) {
                        canAssumeGood = false;
                        break;
                    }
                }
                if (canAssumeGood) {
                    isGoodFlag_[index] = 1;
                    // set as his statement
            
                    auto& currentStatement = statements[index];
                    for (int i=0;i<n_;++i) {
                        if (currentStatement[i] == 1) {
                            isGoodFlag_[i] = 1;
                        }
                        if (currentStatement[i] == 0) {
                            isGoodFlag_[i] = 0;
                        }
                    }

                    TraceBack(statements, index+1);
                    // remember to trace back because we changed the flag vec
                    isGoodFlag_ = isGoodFlag_bak;
                } else {
                    // can not assume him good
                    ;
                }
            }

            // assume him bad, just go on
            if (1) {
                isGoodFlag_[index] = 0;
                TraceBack(statements, index+1);
                // remember to trace back because we changed the flag vec
                isGoodFlag_[index] = 2;
            }
        }

        return true;
    }
};
// @lc code=end

// [[2,0,2,2,0],[2,2,2,1,2],[2,2,2,1,2],[1,2,0,2,2],[1,0,2,1,2]]